package m202401.d07;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/1/7 10:31
 */
public class Q146 {
    class LRUCache {


        private int capacity;
        private Node head;
        private Node tail;

        private Map<Integer, Node> map;


        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.head = new Node();
            this.tail = new Node();
            this.head.next = tail;
            this.tail.pre = head;
            this.map = new HashMap<>();
        }

        public int get(int key) {
            if (!this.map.containsKey(key)) {
                return -1;
            }
            Node node = this.map.get(key);
            update(node);
            return node.value;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.value = value;
                update(node);
                return;
            }
            Node node = new Node();
            node.key = key;
            node.value = value;
            node.next = head.next;
            node.pre = head;
            head.next = node;
            node.next.pre = node;
            map.put(key, node);
            if (map.size() > capacity) {
                Node pre = tail.pre;
                tail.pre = pre.pre;
                pre.pre.next = tail;
                pre.next = null;
                pre.pre = null;
                map.remove(pre.key);
            }
        }

        private void update(Node node) {
            node.next.pre = node.pre;
            node.pre.next = node.next;
            node.next = this.head.next;
            node.pre = this.head;
            node.next.pre = node;
            this.head.next = node;
        }


        class Node {
            public int key;
            public int value;
            public Node next;
            public Node pre;
        }
    }
}
